Count number of nice subarray [Subarrays with K Different Integers]

Time: O(N); Space: O(K); medium

Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

Example 1:

Input: nums = [1,1,2,1,1], k = 3

Output: 2

Explanation:

• The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2:

Input: nums = [2,4,6], k = 1

Output: 0

Explanation:

• There is no odd numbers in the array.

Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2

Output: 16

Constraints:

• 1 <= len(nums) <= 50000

• 1 <= nums[i] <= 10^5

• 1 <= k <= len(nums)

Hints:

1. After replacing each even by zero and every odd by one can we use prefix sum to find answer ?

2. Can we use two pointers to count number of sub-arrays ?

3. Can we store indices of odd numbers and for each k indices count number of sub-arrays contains them ?

class Solution1(object):
    """
    Time: O(N)
    Space: O(K)
    """
    def numberOfSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def atMost(nums, k):
            result, left, count = 0, 0, 0

            for right in range(len(nums)):
                count += nums[right] % 2

                while count > k:
                    count -= nums[left] % 2
                    left += 1
                result += right - left + 1

            return result

        return atMost(nums, k) - atMost(nums, k-1)

s = Solution1()

nums = [1,1,2,1,1]
k = 3
assert s.numberOfSubarrays(nums, k) == 2

nums = [2,4,6]
k = 1
assert s.numberOfSubarrays(nums, k) == 0

nums = [2,2,2,1,2,2,1,2,2,2]
k = 2
assert s.numberOfSubarrays(nums, k) == 16

2. Use Deque

import collections

class Solution2(object):
    def numberOfSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        result = 0

        dq = collections.deque([-1])

        for i in range(len(nums)):
            if nums[i] % 2:
                dq.append(i)
            if len(dq) > k + 1:
                dq.popleft()
            if len(dq) == k + 1:
                result += dq[1] - dq[0]

        return result

s = Solution2()

nums = [1,1,2,1,1]
k = 3
assert s.numberOfSubarrays(nums, k) == 2

nums = [2,4,6]
k = 1
assert s.numberOfSubarrays(nums, k) == 0

nums = [2,2,2,1,2,2,1,2,2,2]
k = 2
assert s.numberOfSubarrays(nums, k) == 16

See also:

https://leetcode.com/problems/count-number-of-nice-subarrays